//链表的回文结构
//对于一个链表，请设计一个时间复杂度为O(n), 
//额外空间复杂度为O(1)的算法，判断其是否为回文结构

#include<stdio.h>
#include<stdlib.h>


struct ListNode
{
	int val;
	struct ListNode* next;
};

void SLTNodePrintf(struct ListNode* ps)
{
	struct ListNode* cur = ps;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
//方法1  整体反转  然后依次判断空间复杂度为On  不符合要求
//int  chkPalindrome(struct ListNode* head)
//{
//	struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
//	//反转
//	struct ListNode* n1, * n2, * n3=NULL;
//	
//	n1 = NULL ;
//	n2 = head;
//	if(n2!=NULL)
//		n3 = n2->next;
//	while (n2)
//	{
//		n2->next = n1;
//		n1 = n2;
//		n2 = n3;
//		if (n3 != NULL)
//			n3 = n3->next;
//	}
//	newhead = n1;
//	//比较
//
//	while (head)
//	{
//		if (head->val != newhead->val)
//		{
//			return 0;
//		}
//		head = head->next;
//		newhead = newhead->next;
//	}
//	return 1;
//
//}
struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* n1 = NULL, * n2 = NULL, * n3 = NULL;
	n1 = NULL;
	n2 = head;
	if (n2 != NULL)
		n3 = n2->next;

	while (n2)
	{
		n2->next = n1;
		n1 = n2;
		n2 = n3;
		if (n3 != NULL)
			n3 = n3->next;
		
	}
	return n1;
}

//思路二  找到中间结点(快慢指针)  逆置后半部分 然后进行判断
int chkPalindrome(struct ListNode* A)
{
	struct ListNode* head = A;
	//找中间结点
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	while (fast!=NULL &&fast->next!=NULL)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	struct ListNode* midode = slow;
	//逆置
	struct ListNode*  NewMidNode = reverseList(midode);
	//判断
	while (NewMidNode)
	{
		if (head->val != NewMidNode->val)
			return 0;
		head = head->next;
		NewMidNode = NewMidNode->next;
	}
	return 1;


}


int main()
{
	struct ListNode* n1 = malloc(sizeof(struct ListNode));
	struct ListNode* n2 = malloc(sizeof(struct ListNode));
	struct ListNode* n3 = malloc(sizeof(struct ListNode));
	struct ListNode* n4 = malloc(sizeof(struct ListNode));

	n1->val = 1;
	n2->val = 3;
	n3->val = 3;
	n4->val = 1;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	SLTNodePrintf(n1);

	int  ret = chkPalindrome(n1);

	if (ret == 1)
	{
		printf("\nYES");
	}
	else
	{
		printf("\nNO");
	}

	return 0;
}